package item16;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Lv Jing
 * @date 2018年07月16日 23:09
 */
public class Power {

    /**
     * 指数、幂都是正数
     * 指数为负数，幂为正数&幂为负数，幂为0
     * 指数为0，幂为正数，幂为负数，幂为0
     */
    @Test
    public void test01() {
        Solution solution = new Solution();
        Assert.assertEquals(4294967296D, solution.Power(2, 32));
        Assert.assertEquals(0.125, solution.Power(2, -3));
        Assert.assertEquals(0.0, solution.Power(0, -3));
        Assert.assertEquals(-0.125, solution.Power(-2, -3));
        Assert.assertEquals(0D, solution.Power(0, 5));
        Assert.assertEquals(0D, solution.Power(0, -5));
        Assert.assertEquals(1D, solution.Power(0, 0));
        Assert.assertEquals(1D, solution.Power(2, 0));
    }
}

class Solution {

    /**
     * 面试题16：求数值的整数次方 base的exponent次方
     * 思路:这道题直接看是很简单的，直接遍历然后相乘即可，但是有几个边界条件需要考虑。
     * 1.指数为负数：这种情况可以先对指数求绝对值，然后当正数处理，求完结果后再求倒数即可。
     * 2.幂为0的情况：0求倒数是没有意义的，所以要排除指数为负数，幂为0的情况；同时指数为0也是没有意义
     * 3.幂为1的情况，这种情况可以不用再进行求幂次方，最后结果肯定是1
     */
    public double Power(double base, int exponent) {
        if (base == 0 && exponent < 0) {
            return 0;
        }
        int absExponent = exponent;
        if (exponent < 0) {
            absExponent = -exponent;
        }
        double result = PowerWithUnsignedExponent(base, absExponent);
        if (exponent < 0) {
            result = 1 / result;
        }
        return result;
    }

    private double PowerWithUnsignedExponent(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        double result = PowerWithUnsignedExponent(base, exponent >> 1);
        result *= result;
        if ((exponent & 1) == 1) {
            result *= base;
        }
        return result;
    }
}
